In recent years, kicked off by diffusion of mobile phones, commercial realization as well as research and development of mobile security technology have increased. Advances have been made in studies of next-generation mobile communication networks that could seamlessly integrate radio transmission having various characteristics, such as a cellular network of 2G or 3G, and that are disclosed, for example, in a non-patent document 1 by the present inventors.
The next-generation communication networks have the capability of automatically selecting optimal radio transmission according to mobile service to be used, and the architecture as disclosed in a non-patent document 2 in which various radio transmissions are able to plug in a same network in a flexible manner is assumed.    Non-Patent Document 1: M. Kuroda, M. Inoue, A. Okubo, T. Sakakura, K. Shimizu, and F. Adachi, “Scalable Mobile Ethernet and Fast Vertical Handover,” Proc. IEEE Wireless Communications and Networking Conference 2004, March 2004.    Non-Patent Document 2: M. Yoshida, M. Kuroda, S. Kiyomoto, and T. Tanaka, “A Secure Service Architecture for Beyond 3G Wireless Network,” Proc. 6th International Symposiumon Wireless Personal Multimedia Communications, Vol. 2, pp. 579-583, 2003.
In a next-generation mobile communication network, expectations are placed on not only conventional services of the client-server type but also services of a group type wherein a plurality of users use a variety of portable terminals and form a dynamic group whereby the members can securely share information with each other. Although the capabilities required for implementing such secure group communications include confidentiality of data, verification of integrity, authentication of a sender, management of members, etc., management of a group key to be shared by group members is a critical study subject as well.
In a dynamic group which members can possibly join/leave, a group key should be updated so that a member who newly joins a group (hereinafter referred to as a joining member) cannot gain access to any information before he/she joins or a member who leaves a group (hereinafter referred to as a leaving member) cannot gain access to any information after he/she leaves.
The key management scheme capable of updating a group key is roughly divided into the following: a scheme that needs a server for intensively managing a key or radio stations (as disclosed in a non-patent document 3 or 11), and a scheme known as Contributory Key Agreement in which all group members cooperate in sharing a DH key and update a group key (as disclosed in a non-patent document 12 or 16).
Needless to say, sharing of the DH key is the key sharing scheme developed by (Mr.) Diffie and (Mr.) Hellman that utilizes a discrete logarithm problem and communicates published information (a public key) generated from random numbers and a secret key, and not a secret key itself. This could prevent a secret key from being decrypted (known) immediately even if a third person wiretapped communication, thereby making it possible to ensure key information to be shared securely.    Non-Patent Document 3: H. Harney, C. Muckenhirn, and T. Rivers, “Group Key Management Protocol (GKMP) Specification,” IETF, RFC 2093, 1997.    Non-Patent Document 4: H. Harney, C. Muckenhirn, and T. Rivers, “Group Key Management Protocol (GKMP) Architecture,” IETF, RFC 2094, 1997.    Non-Patent Document 5: D. Wallner, E. Harder, R. Agee, “Key Management for Multicast: Issues and Architectures,” IETF, RFC 2627, 1999.    Non-Patent Document 6: C. K. Wong, M. Gouda, and S. Lam, “Secure Group Communication Using Key Graphs,” IEEE/ACM Trans. on Networking, Vol. 8, No. 1, pp. 16-30, 2000.    Non-Patent Document 7: R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas, “Multicast Security: A Taxonomy and Efficient Constructions,” Proc. IEEE Infocom '99, Vol. 2, pp. 708-716, 1999.    Non-Patent Document 8: D. A. McGrew, and A. T. Sherman, “Key Establishment in Large Dynamic Groups Using On-Way Function Trees,” IEEE Trans. on Software Engineering, Vol. 29, No. 5, pp. 444-458, 2003.    Non-Patent Document 9: A. Perrig, D. Song, and J. D. Tygar, “ELK: A New Protocol for Efficient Large-Group Key Distribution,” Proc. IEEE Security and Privacy Symposium, pp. 247-262, 2001.    Non-Patent Document 10: A. Perrig, R. Szewczyk, V. Wen, D. Culler, and J. D. Tygar, “SPINS: Security Protocols for Sensor Networks,” Proc. Mobile Computing and Networking 2001, pp. 189-199, 2001.    Non-Patent Document 11: Y. W. Law, R. Corin, S. Etalle, and P. H. Hartel, “A Formally Verified Decentralized Key Management Architecture for Wireless Sensor Networks,” Proc. Personal Wireless Communications 2003, pp. 27-39, 2003.    Non-Patent Document 12: D. G. Steer, L. Strawczynski, W. Diffie, and M. Wiener, “A Secure Audio Teleconference System,” Proc. Advances in Cryptology-CRYPTO '88, pp. 520-528, 1988.    Non-Patent Document 13: M. Burmester, and Y. Desmedt, “A Secure and Efficient Conference Key Distribution System,” Proc. Advances in Cryptology-EUROCRYPT '94, pp. 275-286, 1994.    Non-Patent Document 14: M. Steiner, G. Tsudik, and M. Waidner, “Key Agreement in Dynamic Peer Groups,” IEEE Trans. On Parallel and Distributed Systems, Vol. 11, No. 8, pp. 769-780, 2000.    Non-Patent Document 15: J. Alves-Foss, “An Efficient Secure Authenticated Group Key Exchange Algorithm for Large and Dynamic Groups,” Proc. 23rd National Information Systems Security Conference, pp. 254-266, 2000.    Non-Patent Document 16: Y. Kim, A. Perrig, and G. Tsudik, “Simple and Fault-Tolerant Key Agreement for Dynamic Collaborative Groups,” ACM Conference on Computer and Communications Security 2000, pp. 235-244, 2000.
In the former scheme, an entity that intensively manages the key may possibly be a Single Point of Failure, and is difficult to apply to serverless group communications such as an Ad Hoc network, etc. In the latter scheme, all group members are required to execute a power-residue operation when updating a group key, which is unfit for group communications including portable terminals with poor calculating ability, etc.
As the conventional method of updating a group key, a scheme known as Logical Key Hierarchy (LKH) (disclosed in non-patent documents 5 and 6) that manages a key in a tree structure is highly effective.
However, not only such the method of intensively managing the key suffers from the problems described above, but also a key management scheme that involves less cost when a member joins or leaves is anticipated.
As a patent document that uses a key management server, the technology disclosed in a patent document 17 or 18 has been known. The patent document 17 discloses a scheme in which a key management server exercises collective control, and then there is a problem that updating a key becomes more costly if a group involved has a large scale. In the patent document 18, a sub-group key management server that manages sub-groups is separately provided. However, because the server only manages a key, a server at higher level in the tree structure manages.    Patent Document 17: Japanese Patent Application Laid-Open No. 9-319673    Patent Document 18: Japanese Patent Application Laid-Open No. 2004-023237